#include<iostream>

const int capacity=10;
class MaxHeap
{
public:
    MaxHeap():size(0){}
    void Insert(int value)
    {
        if(size==capacity)
            return;
        array[size]=value;
        sifwUp(size);
        size++;
    }
    void Remove()
    {
        if(size==0)
            return;
        array[0]=array[--size];
        siftDown(0);

    }
    int *GetRoot()
    {
        if(size==0)
            return nullptr;
        return &array[0];
    }
    void show()
    {
        for(int i=0;i<size;i++)
        {
            std::cout<<array[i]<<" ";
        }
        std::cout<<std::endl;
    }


private:
    int GetParent(int i){return(i-1)/2;}
    int GetLeftChild(int i){ return 2*i+1;}
    int GetRightChile(int i){return 2*i+2;}
    void sifwUp(int i)//上浮操作  O(logn)
    {
        while(i>0&&array[i]>array[GetParent(i)])
        {
            std::swap(array[i],array[GetParent(i)]);
            i=GetParent(i);
        }
    }
    void siftDown(int i)//下沉操作
    {
        int left=GetLeftChild(i);
        int right=GetRightChile(i);
        int max=i;
        if(left<size&&array[left]>array[max])
        {
            max=left;
        }
        if(right<size&&array[right]>array[max])
        {
            max=right;
        }
        if(max!=i)//i下沉了
        {
            std::swap(array[i],array[max]);
            siftDown(max);//递归下沉；
        }
    }
    int array[capacity];
    int size;
};


int main()
{
    MaxHeap h;
    for(int i=0;i<10;i++)
    {
        h.Insert(i+1);

    }
    h.show();
    h.Remove();
    h.show();
    return 0;
}